Fritz: All Fritz/All Fritz.zip/All Fritz/FILES/WORDMISC/FLYSTEXP.LZH/FLYSTEXP.DOC

Text File | 2001-01-01 | 19KB | 364 lines

Introduction (and a little rattling of the cup...)

     st/exp represents a new level of performance for text data compression,
typically compressing text files to about 30% of their original size.
However, high throughput is not sacrificed in the process; it is competitive
in speed with the best programs based upon the vastly simpler Limpel-Ziv
algorithm.

     I believe it recognizes a point seemingly passed over in all the other
attempts at text data compression that I know of.  Namely, that the pursuit
of ever higher storage capacities without, at the same time, addressing more
convenient information ACCESS, is ultimately a pursuit that will end in
chaos.  The word-orientation of st/exp's compression technique provides the
"hooks" to address exactly this issue of convenient information access.

     But, st/exp is not all there is to this package.  There's also what I
consider to be a great little utility, albeit a DIFFERENT little utility,
that takes a lot of the busywork out of word-processing.  I'm using it right
now, along with Microsoft Word, to write this.  It's called Typing Demon.

     If you take a little time to understand what it does, I suspect that
you'll like it, too.  If you just jump into it, it will probably beep at you
a lot, and you'll probably find it weird and frustrating.  It's really not
that difficult to get used to.  Getting used to not having it, if someone
shoves you onto a VAX or something, would be more difficult.

     There's also a nice directory program, as well as a number of other
programs which, likely as not, duplicate programs you already have.

     If you find these programs useful, a contribution of $25 will be
greatly appreciated.  For $50, you will be registered and will receive the
next program update, with manual, at no additional cost.  Quantity discounts
and site licensing can be worked out for anyone that gets really serious
about it.

     st/exp was definitely NOT a hobbyist effort.  I'm trying to do this for
a living.  With your support, Bartles and James has been able to bring you
an ever-expanding array of different-flavored wine coolers.  Also with your
support, I will be able to continue to develop this basic technology into
something that will be even more useful and interesting, which will
ultimately save YOU money!  You can send your INVESTMENT to:

     MicroComputer Square
     126 Hancock Avenue
     Spartanburg, SC  29302

and THANKS!!!


     PLEASE NOTE that your contribution entitles you to ALL of the programs
listed below, even though the package may be broken up in archives named
fly_util.arc, flydemon.arc, and flystexp.arc, to allow downloading in smaller
"bytes".


Now the Manual

The following programs and files should be found on the distribution disks:

ask_demo.bat  -- provides a demonstration of the ask program
ask.exe       -- a UNIX-style utility for use in batch files
d.exe         -- a directory program you'll like
hide.exe      -- changes the attribute of the specified file to "hidden"
hunt.exe      -- a file-name finder utility
look4.exe     -- searches for any file containing a specified text string
mc2sp.exe     -- Installs MicroComputer Square's sexy prompt
newdate.exe   -- changes the file date/time of the specified files
unhide.exe    -- changes the attribute of the specified file to "normal"
volname.exe   -- allows you to name/rename a disk (hard or floppy) volume

All of the above programs provide at least minimal instruction as to how to
run them, simply by typing their program name (followed by return).  One
exception is mc2sp, which simply does its thing (which is to write a prompt
command to your autoexec file).  The other exception is d, our directory
program.  d will provide rather complete help, by typing "d h", or "d ?".

These files are in the directory "DEMON"

demon.exe     -- the Typing Demon program
linguist.exe  -- a vocabulary-analysis program for use with Typing Demon
mk_demon.exe  -- a "compiler" program to generate your own list of demons
                   and abbreviations for use with Typing Demon
setdemon.exe  -- configures Typing Demon according to its options

demons.fly    -- the compiled distribution "demons file" for fanatics
template.fly  -- the ASCII source file for the above
demons.qwe    -- the compiled demons file for the QWERTY keyboard
template.qwe  -- the ASCII source file for the above

As above, most of these programs provide some minimal help by typing their
program name.  The Typing Demon program, however, simply installs itself in
memory when its name is typed.

These files are in the directory "STEXP"

st.exe        -- the FlySpeed compression program
exp.exe       --  "     "     expansion program
flyspeed.mc2  -- FlySpeed's dictionary data file

st/exp will tell you that you need to specify a file-specification, if you
simply type their program name, followed by return.


st/exp

     st/exp (es-tee-e-x-p) is really a pair of programs: st.exe, which
compresses text files (we had to call it something, so we called it "stomp",
or "st" for short), and exp.exe (short for "expand"), which re-expands the
compressed file to an identical copy of the original.  By "text", we mean
the normal output of word-processing programs, preferably saved in a stan-
dard ASCII format (as is usually done for telecommunications use).  Eventu-
ally, the program should be able to reliably compress database files as well
(and maybe spreadsheet files a little later), but for now we intend to
concern ourselves with compression of written language, which is actually a
more difficult problem that really has not been adequately addressed, until
now.

How It Works

     Well, we can't entirely say, since some aspects of the program's opera-
tion constitute patentable processes, and the patent application hasn't been
filed yet.  Beyond that, the program simply doesn't work by any one simple
"trick" or "scheme"; it is actually a collection of algorithms, some novel
and wretchedly complex, with an efficient means of determining the best
algorithm to use for the data immediately being examined.  For example, the
well-known (in computing circles) run-length-limited representation is used
to optimally represent situations in which a particular character is repeat-
ed a number of times, such as a long sequence of spaces.  We expect that the
program will eventually be able to compress database files quite well, since
spaces or "null characters" are often employed as fill characters for "empty
fields" in database files, and these sequences can be compressed to just
about nothing using a run-length representation.  Compression of true text
data, which is to say written language in a digital form, is not so easily
accomplished, unfortunately.

     (Those of you who are particularly interested in compression of data-
base and spreadsheet files should make your interests known to us.  We would
especially appreciate any actual dBase II and Lotus files you care to send
us, since lack of actual data to use for tests is one of the most serious
impediments to the development and refinement of that capability.)

     We have described Fly Coding as an "optimal representation of lan-
guage", implicitly meaning "an optimal digital representation of written
language", including punctuation, etc.  The use of the word "optimal" na-
turally begs the question, "Optimal in what sense?", or "What parameter or
parameters are being optimized?"

A Real-Quick Tutorial on Digital Data Storage

     Computer people like to talk in terms of bits and bytes.  A BIT is a
Binary digIT, which can be either a 0 or a 1, easily represented electron-
ically as a low (less than 1 Volt) or high (more than 3 Volts) voltage.
Since a bit is so little (it takes about 10 to make the equivalent of 3
normal, base-10 digits), a byte (which is 8 bits) is generally more conven-
ient to talk about.

     A byte can represent 2-to-the-power-of-8, or 256, different values, and
may thus be thought of as a digit, base-256, or by "hexadecimal" notation:
two digits, base-16.

     If, say, the Declaration of Independence, stored as a normal text file,
contained 10,000 bytes, then, in effect, we are using a 10,000 digit number,
base-256, to represent the information contained in the Declaration of
Independence (a number vastly larger than the number of subatomic particles
in the universe).  This would be exactly equivalent to 20,000 digits, base-
16, and approximately 24,000 digits, base-10 (since "5 digits", 100,000
base-16, is 1,048,576 or about "6 digits", base-10).

     What we would like to do is to find a number with significantly fewer
digits which can represent the same information, thereby reducing the space
required to store the number, whether we are storing it on a piece of paper,
or a magnetic or optical disk (and also reducing the time it will take to
transmit the number by modem).  If we can reduce the number of digits needed
by a factor of 4, then, in effect, we are transforming the number into a
second number which is approximately the fourth root of the first (we must,
of course, be able to transform the second number identically back into the
first).

     We would like to say that, in producing an "optimal representation of
language", we have found a way of finding the minimum number which can
represent a given document.  We think we can make this statement, with the
qualification that the technique should not resort to natural-language
comprehension in order to perform the compression.

     This qualification hints at the other parameters which are of concern:
namely, the speed at which the process operates, as well as its memory
requirements, reliability, and certainly the feasibility of accomplishing
the desired goal before starvation set in.  In other words, what is being
optimized is the USEFULNESS of the technique, which is a more subtle issue
than just optimizing the compression factor.  Nonetheless, we feel that we
were able to avoid all, but a few minor compromises between high compression
factor and high throughput.

But How Does It Work?

     In order to discuss "how it works" adequately, some discussion of "what
information is", from an epistemological perspective, is in order.  But
since we've probably already lost some of you, we'd really rather not go
into that...

     However, an explanation that we think will satisfy a lot of people, and
which really does explain much of how the program works, is simply this:

     The program uses a "dictionary", contained in the file "flyspeed.mc2",
to convert words found in a document to numbers, which take up less room
than the original word, as represented according to the standard convention.

     The dictionary, itself, employs data-compression techniques, as do the
dictionaries used in spelling checkers that come with most word-processing
packages.  The difference is that, while the data-compression techniques
employed in common spelling checkers are oriented toward anachronistic
concerns over saving memory, the data-compression techniques employed in
FlySpeed's dictionary are geared toward high-speed lookup.  It is for this
reason that FlySpeed's "tokenizing engine" runs from 19 (Wordperfect) to 115
(Borland's Turbo Lightning) times faster than typical spelling checkers on
the market.

     A writer of an ad which appeared recently in a major personal-computing
publication, for a board which compresses database files, had "cutesie"
compression programs mashing, mangling, and otherwise doing terrible things
to data.  (We're not sure what's so different about having the micropro-
cessor on your computer's motherboard do the compression, from having a
microprocessor on a plug-in board, if you have any plug-in slots left... do
it.)  It fairly well pointed up the fact that most people haven't got a clue
as to what data-compression really means.

     In a nutshell, data-compression simply means finding a more efficient
representation of data than the representation commonly in use, and being
able to translate back and forth between the two.  There is usually nothing
which intrinsically recommends "the representation commonly in use", other
than simplicity and expediency.  We feel that, given the power and sophis-
tication of modern microcomputers, simplicity and expediency no longer
constitute sufficient justification for the use of ASCII (American Standard
Code for Information Interchange), at least not for the purposes of infor-
mation storage and communication.  Furthermore, as businesses are beginning
to build up megabytes of records and documents on their computers, there is
a need not only to address efficient information storage and communication,
but efficient information retrieval, as well.

Running st/exp

     st and exp must be run from the directory in which they are located
(you can't simply put them in some directory named in a "path command", and
then run them from whatever directory you happen to be in).

     We could eliminate this restriction, and we'll do so if people scream
for it, but the programs load somewhat faster when DOS doesn't have to look
very far for them.  For short documents, the time it takes DOS simply to
load st/exp, can be a significant portion of the program's "run time".

     Besides, you'll compress files after you've finished creating them, at
which time you'll probably be in your word-processing directory, so your
word-processing directory is the logical place to put st/exp.

In order to compress a file, simply type:

     st filename

More generally, you can type:

     st filespec1 ... filespecN

in order to compress all files having those file-specifications.  For
example, you would type :

     st \mary\*.doc john\*.txt gossip?.*

in order to compress all files in the directory "mary", having the extension
"doc"; all files in the subdirectory "john", of the current directory, hav-
ing the extension "txt", as well as all files in the current directory with
any extension, and whose first six characters are "gossip".

     Expansion works in a similar fashion; however, exp always looks for
files having a "prs" extension (which is the extension assigned by st to its
compressed output file).  Thus, in order to expand the files above, you
would type:

     exp \mary\* john\* gossip?

     By September '88, we expect to provide an option by which Typing Demon
can automatically compress your files when you leave your word-processor.
We will also provide an archive capability, wherein many documents are
packed into a single large file.  (When DOS stores a file, it stores it in
an integral number of "clusters" of disk-sectors.  A common cluster size for
hard-disks is 16 sectors, or 8192 bytes, so that up to 8191 bytes are wasted
when DOS stores a file.)  This archive capability will also be important for
our text-retrieval program, Merlin, which will allow you to access files by
any word, or combination of words, in the archive.


A Nasty Footnote about Microsoft Word

     We hope this isn't going to get to be a regular thing with Microsoft
Word, but, as with Typing Demon, we need to add a footnote...

     If you get out your calculator and divide the file-size of your Word
documents by 512, you'll always end up with an integer.  This is not due to
some great coincidence of the Cosmos.  Since the sector size used by IBM PCs
is 512 bytes, they may have decided that it doesn't "hurt anything" to do
this.  Even if you plan to transmit the document by modem, with a 1200 baud
modem, it would take only about an extra 4 seconds to transmit the maximum
511 bytes of unnecessary junk left at the end of the file.

     However, since st/exp is not at liberty to decide what in a file is and
is not important, when it encounters this junk, it must faithfully deal with
it.  This can have a disproportionate impact in the compression one may
achieve with Microsoft Word files, particularly for files with perhaps only
1000 words, and 511 bytes of junk at the end.

     One solution is to store your Word documents on disk in the standard
ASCII format, by setting the printer to "plain", and printing to a file as
described in the Word manual.  You may need to do this anyway, if you are
sending electronic mail to someone who doesn't have Microsoft Word.  How-
ever, Word is not especially fast at saving documents in text form.

     The best solution, which is out of your hands as well as ours, is for
Microsoft to set the file-size to its real value, or, at least, set all the
junk to spaces or nulls.

     Where all this junk comes from, this writer isn't entirely certain.  I
noticed once, that one Word file I'd just written had junk from a previous
file I'd been working on, which suggests that the junk is simply whatever
happened to be in some particular section of memory when the file was saved.

     So, if you're using Microsoft Word to write some electronic mail to
someone you and a co-conspirator are planning to murder, and you're also
writing to your co-conspirator, write your letter to your co-conspirator
AFTER you write the letter to your intended victim.

     Conversely, if you suspect that someone is conspiring to murder you,
and you get some electronic mail from them written with Word, type the file
to the screen to display any junk which might be at the end.  It may just
contain a fragment of some mail written previously to their co-conspirator,
which may give their plan away, and provide evidence for the authorities.

     In addition to this junk at the end of a Word file, there is also a
128-byte header at the beginning of Word files, which appears to contain
useful information (at least useful to Word itself), such as what the right-
hand margin setting for the file is.  Of course, having to deal with this
non-language information also can hurt the compression attainable with
Microsoft Word, though it doesn't cause that much of a problem for longer
files.


Installation

     Most FlySpeed programs are programs you will want to run without
actually having to be in the directory in which they are located.  I have
two subdirectories, one named "dos" and the other named "batch", which I
have made "globally visible" (I can invoke the programs and batch files in
them no matter what the current subdirectory may be) by means of a path
command (see your DOS manual if you don't know what that is).  I think it
would be just as good to lump them all together in a directory named
"global", for that matter.  Listed below is the recommended place to put the
various programs, where "global" means some directory which is normally
included in a path command (which you will probably have in your
autoexec.bat file).

In the directory "STEXP" ...

st            -- Probably in your word-processing directory.
exp           -- ditto.
flyspeed.mc2  -- ditto.